package com.leetcode.test.tree;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;

public class 后序遍历 extends 二叉树Case {

	@Test
	public void test() {
//		1
//       \
//		  2
//		 /
//		3
		TreeNode node1 = new TreeNode(1);
		TreeNode node2 = node1.right = new TreeNode(2);
		TreeNode node3 = node2.left = new TreeNode(3);

		Assert.assertEquals(Arrays.asList(3, 2, 1), postorderTraversal(node1));
	}

	@Test
	public void test2() {
		CharTreeNode nf = new CharTreeNode('F');
		CharTreeNode nb = nf.left = new CharTreeNode('B');
		CharTreeNode na = nb.left = new CharTreeNode('A');
		CharTreeNode nd = nb.right = new CharTreeNode('D');
		CharTreeNode nc = nd.left = new CharTreeNode('C');
		CharTreeNode ne = nd.right = new CharTreeNode('E');
		CharTreeNode ng = nf.right = new CharTreeNode('G');
		CharTreeNode ni = ng.right = new CharTreeNode('I');
		CharTreeNode nh = ni.left = new CharTreeNode('H');

		CharTreeNode root = nf;

		Assert.assertEquals(Arrays.asList('A', 'C', 'E', 'D', 'B', 'H', 'I', 'G', 'F'), postorderTraversal(root));
	}

	/**
	 * 后序遍历
	 */
	public List<Integer> postorderTraversal(TreeNodeT root) {
		List<Integer> res = new ArrayList<>();
		help(root, res);
		return res;
	}

	private void help(TreeNodeT node, List res) {
		if (node == null) {
			return;
		}

		if (node.left != null) {
			help(node.left, res);
		}
		if (node.right != null) {
			help(node.right, res);
		}
		res.add(node.val);
	}
}
